home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / 1991 / 02 / nelson / bill.c next >
C/C++ Source or Header  |  1990-06-03  |  6KB  |  200 lines
  1. /*
  2.  * Listing 5 -- bill.c
  3.  *
  4.  * This short demonstration program will use arithmetic data
  5.  * compression to encode and then decode a string that only uses
  6.  * the letters out of the phrase "BILL GATES".  It uses a fixed
  7.  * table of probabilities that is hardcoded in.  Note that it
  8.  * differs from the example in the article in that it adds a single
  9.  * new symbol, '\0', which is used to indicate the end of the string.
  10.  *
  11.  * To build this program:
  12.  *
  13.  * Turbo C:     tcc -w bill.c bitio.c coder.c
  14.  * QuickC:      qcl /W3 bill.c bitio.c coder.c
  15.  * Zortech:     ztc bill.c bitio.c coder.c
  16.  * *NIX:        cc -o bill bill.c bitio.c coder.c
  17.  *
  18.  */
  19.  
  20. #include <stdio.h>
  21. #include <stdlib.h>
  22. #include "coder.h"
  23. #include "bitio.h"
  24.  
  25. /*
  26.  * Declarations for local routines.
  27.  */
  28. void compress( void );
  29. void expand( void );
  30. void convert_int_to_symbol( char c, SYMBOL *s );
  31. char convert_symbol_to_int( unsigned int count, SYMBOL *s );
  32. void error_exit( char *message );
  33.  
  34. /*
  35.  * This is a the probability table for the symbol set used
  36.  * in this example.  Each symbols has a low and high range,
  37.  * and the total count is fixed at 11.
  38.  */
  39. struct {
  40.           char c;
  41.           unsigned short int low;
  42.           unsigned short int high;
  43.        } probabilities[]= {{ 'B',  0,  1  },
  44.                            { 'I',  1,  2  },
  45.                            { 'L',  2,  4  },
  46.                            { ' ',  4,  5  },
  47.                            { 'G',  5,  6  },
  48.                            { 'A',  6,  7  },
  49.                            { 'T',  7,  8  },
  50.                            { 'E',  8,  9  },
  51.                            { 'S',  9,  10 },
  52.                            { '\0', 10, 11  }
  53.                           };
  54. /*
  55.  * This example program compresses an input string, sending
  56.  * the output to a file.  It then expands the output file,
  57.  * sending the decoded characters to the screen.
  58.  */
  59. void main()
  60. {
  61.     compress();
  62.     expand();
  63. }
  64.  
  65. /*
  66.  * This is the compress routine.  It shows the basic algorithm for
  67.  * the compression programs used in this article.  First, an input
  68.  * characters is loaded.  The modeling routines are called to
  69.  * convert the character to a symbol, which has a high, low and
  70.  * range.  Finally, the arithmetic coder module is called to
  71.  * output the symbols to the bit stream.
  72.  */
  73. void compress()
  74. {
  75.     int i;
  76.     char c;
  77.     SYMBOL s;
  78.     FILE *compressed_file;
  79.     static char *input = "GLIB BATES";
  80.  
  81.     compressed_file=fopen( "test.cmp", "wb" );
  82.     if ( compressed_file == NULL )
  83.         error_exit( "Could not open output file" );
  84.     puts( "Compressing..." );
  85.     initialize_output_bitstream();
  86.     initialize_arithmetic_encoder();
  87.     for ( i=0 ; ; )
  88.     {
  89.         c = input[ i++ ];
  90.         convert_int_to_symbol( c, &s );
  91.         encode_symbol( compressed_file, &s );
  92.         if ( c == '\0' )
  93.             break;
  94.     }
  95.     flush_arithmetic_encoder( compressed_file );
  96.     flush_output_bitstream( compressed_file );
  97.     fclose( compressed_file);
  98. }
  99.  
  100. /*
  101.  * This expansion routine demonstrates the basic algorithm used for
  102.  * decompression in this article.  It first goes to the modeling
  103.  * module and gets the scale for the current context.  (Note that
  104.  * the scale is fixed here, since this is not an adaptive model).
  105.  * It then asks the arithmetic decoder to give a high and low
  106.  * value for the current input number scaled to match the current
  107.  * range.  Finally, it asks the modeling unit to convert the
  108.  * high and low values to a symbol.
  109.  */
  110. void expand()
  111. {
  112.     FILE *compressed_file;
  113.     SYMBOL s;
  114.     char c;
  115.     int count;
  116.  
  117.     compressed_file=fopen( "test.cmp", "rb" );
  118.     if ( compressed_file == NULL )
  119.         error_exit( "Could not open output file" );
  120.     puts( "Decoding..." );
  121.     printf( "Incoming characters: " );
  122.     initialize_input_bitstream();
  123.     initialize_arithmetic_decoder( compressed_file );
  124.     for ( ; ; )
  125.     {
  126.         s.scale = 11;
  127.         count = get_current_count( &s );
  128.         c = convert_symbol_to_int( count, &s );
  129.         if ( c == '\0' )
  130.             break;
  131.         remove_symbol_from_stream( compressed_file, &s );
  132.         putc( c, stdout );
  133.     }
  134.     putc( '\n', stdout );
  135. }
  136.  
  137. /*
  138.  * This routine is called to convert a character read in from
  139.  * the text input stream to a low, high, range SYMBOL.  This is
  140.  * part of the modeling function.  In this case, all that needs
  141.  * to be done is to find the character in the probabilities table
  142.  * and then retrieve the low and high values for that symbol.
  143.  */
  144. void convert_int_to_symbol( char c, SYMBOL *s )
  145. {
  146.     int i;
  147.  
  148.     i=0;
  149.     for ( ; ; )
  150.     {
  151.         if ( c == probabilities[ i ].c )
  152.         {
  153.             s->low_count = probabilities[ i ].low;
  154.             s->high_count = probabilities[ i ].high;
  155.             s->scale = 11;
  156.             return;
  157.         }
  158.         if ( probabilities[i].c == '\0' )
  159.             error_exit( "Trying to encode a char not in the table" );
  160.         i++;
  161.     }
  162. }
  163.  
  164. /*
  165.  * This modeling function is called to convert a SYMBOL value
  166.  * consisting of a low, high, and range value into a text character
  167.  * that can be sent to a file.  It does this by finding the symbol
  168.  * in the probability table that straddles the current range.
  169.  */
  170. char convert_symbol_to_int( unsigned int count, SYMBOL *s )
  171. {
  172.     int i;
  173.  
  174.     i = 0;
  175.     for ( ; ; )
  176.     {
  177.         if ( count >= probabilities[ i ].low &&
  178.              count < probabilities[ i ].high )
  179.         {
  180.             s->low_count = probabilities[ i ].low;
  181.             s->high_count = probabilities[ i ].high;
  182.             s->scale = 11;
  183.             return( probabilities[ i ].c );
  184.         }
  185.         if ( probabilities[ i ].c == '\0' )
  186.             error_exit( "Failure to decode character" );
  187.         i++;
  188.     }
  189. }
  190.  
  191. /*
  192.  * A generic error routine.
  193.  */
  194. void error_exit( char *message )
  195. {
  196.     puts( message );
  197.     exit( -1 );
  198. }
  199.  
  200.